UC知道请挑战:求第K个最大数[可加最多分]
来源：百度知道 编辑：UC知道 时间：2024/05/18 21:55:46
我以我所有的积分求本类型题的解。
有N = 800,000,000个整数,大小随机,未排序,要求出其中第K个最大数.如何求?
要求1 <= K <= 800,000,000.时间限制5s.本题假设K = 400,000,000.
先说明一下:这N个数可能有的数是相等的,但是不能算是一个数.算法必须是O(N)级的才能过.有人说用堆.这个不行,堆的平均复杂度是:O(KLogK + (N – K)).也有人说用仿插入排序法.就是先选取一个中值元素（该中值是否合理将影响到算法效率），然后进行切割，将大于等于该数的元素放到其左侧，小于该数的放到右侧。如7 4 6 8 0 -1 选取6作为中值元素，则结果应该为4 0 -1 6 8 7，接下来比较K值和现在的中值元素6所在索引(3)，如何小于3，则只需在索引0~2间再进行递归操作继续选取第K名，大于3则在4~5中递归选取第K – 3名即可。但是这个需要存储大量的数据,我们的内存是受不了的.呵呵.现在我会给敢于挑战的10个积分,如果谁能完美的解决这个问题,我可以给你我能给的最多的分数.也非常感谢你的!!
题目的来源:http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1119
可能我的思路不正确,如果能解决这个题也行.
有N = 800,000,000个整数,大小随机,未排序,要求出其中第K个最大数.如何求?
要求1 <= K <= 800,000,000.时间限制5s.本题假设K = 400,000,000.
先说明一下:这N个数可能有的数是相等的,但是不能算是一个数.算法必须是O(N)级的才能过.有人说用堆.这个不行,堆的平均复杂度是:O(KLogK + (N – K)).也有人说用仿插入排序法.就是先选取一个中值元素（该中值是否合理将影响到算法效率），然后进行切割，将大于等于该数的元素放到其左侧，小于该数的放到右侧。如7 4 6 8 0 -1 选取6作为中值元素，则结果应该为4 0 -1 6 8 7，接下来比较K值和现在的中值元素6所在索引(3)，如何小于3，则只需在索引0~2间再进行递归操作继续选取第K名，大于3则在4~5中递归选取第K – 3名即可。但是这个需要存储大量的数据,我们的内存是受不了的.呵呵.现在我会给敢于挑战的10个积分,如果谁能完美的解决这个问题,我可以给你我能给的最多的分数.也非常感谢你的!!
题目的来源:http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1119
可能我的思路不正确,如果能解决这个题也行.
O(N)肯定不可能。
我觉得O(N*K) 还差不多。
我的思路是new一个大小为K的数组，然后遍历N数组（N数组就是你给的随机数，暂且认为是数组），依次寻找最大值，填入K数组。得到K数组中按大小顺序存放最大的K个数（没有相同值）
ACMer？这两种算法是我能想到的算法了。good luck
我想利用归并排序的思想来可以解决你的问题
#include<iostream.h>
#define M 10
void main()
{
long n,k,t,a[M];
cout<<"请输入多少个整数？（回车结束）"<<endl;
for(int i=1;i<=M;i++)
cin>>a[i];
cout<<"你想求出第几个最大数？"<<endl;
cin>>k;
for(i=1;i<=k;i++)
for(int j=i+1;j<=M;j++)
if(a[i]<a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
cout<<"第"<<k<<"个最大的数是："<<a[k]<<endl;
}